﻿#include <iostream>
#include <queue>    // 用于层次遍历和层次插入
#include <stack>    // 用于非递归遍历
#include <algorithm> // 用于max函数

template <typename T>
class BinaryTree {
private:
    // 二叉树节点结构体
    struct TreeNode {
        T data;             // 节点存储的数据
        TreeNode* left;     // 左子节点指针
        TreeNode* right;    // 右子节点指针

        // 节点构造函数
        TreeNode(T val) : data(val), left(nullptr), right(nullptr) {}
    };

    TreeNode* root;  // 树的根节点

public:
    // 构造函数：初始化空树
    BinaryTree() : root(nullptr) {}

    // 析构函数：释放所有节点内存
    ~BinaryTree() {
        clear(root);
    }

    // 判断树是否为空
    bool isEmpty() const {
        return root == nullptr;
    }

    // 获取根节点
    TreeNode* getRoot() const {
        return root;
    }

    // ========== 插入操作 ==========

    /**
     * 层次插入 - 按完全二叉树的方式插入
     * 这种方法保持树的完整性，适合构建完全二叉树
     * 
     * 这里先添加根节点1，在添加2时 把前面1 添加到 队列里（先进先出），在遍历队列，取出最前面的数移除，
     * 然后树左边判断，左边开始，如果为NULL,则添加数值，不为空则添加到队列。
       然后右左边判断，右边开始，如果为NULL,则添加数值，不为空则添加到队列。
     * 然后在遍历队列判断是否为空，不为空从前面遍历开始继续循环执行。执行查找到为null的地方插入值
     * 
     * 就是遍历是判断左右两边有没有数据，有则添加到队列，在遍历是弹出看下一层，为null则添加node搭配这个节点
     */
    void levelOrderInsert(T val) {
        // 如果树为空，创建根节点
        if (root == nullptr) {
            root = new TreeNode(val);
            return;
        }

        // 使用队列进行层次遍历，找到第一个可以插入的位置
        std::queue<TreeNode*> q;//先进先出
        q.push(root);

        // 使用队列进行广度优先遍历（层级遍历）
        while (!q.empty()) {
            // 取出队列前端的节点（当前待处理的节点）
            TreeNode* current = q.front();
            q.pop();

            // 先尝试插入左子树
            if (current->left == nullptr) {
                // 如果左子节点为空，在此处插入新节点
                current->left = new TreeNode(val);
                return; // 插入完成后立即返回，结束函数
            }
            else {
                // 如果左子节点不为空，将其加入队列以便后续处理
                q.push(current->left);
            }

            // 再尝试插入右子树
            if (current->right == nullptr) {
                // 如果右子节点为空，在此处插入新节点
                current->right = new TreeNode(val);
                return; // 插入完成后立即返回，结束函数
            }
            else {
                // 如果右子节点不为空，将其加入队列以便后续处理
                q.push(current->right);
            }
        }
    }

    /**
     * 递归插入 - 用户指定父节点和插入方向
     * @param parentVal 父节点的值
     * @param val 要插入的值
     * @param isLeft 是否作为左子节点插入
     * @return 是否插入成功
     */
    bool recursiveInsert(T parentVal, T val, bool isLeft = true) {
        TreeNode* parent = findNode(root, parentVal);
        if (parent == nullptr) {
            std::cout << "未找到父节点 " << parentVal << std::endl;
            return false;
        }

        // 检查要插入的位置是否已有节点
        if (isLeft) {
            if (parent->left != nullptr) {
                std::cout << "左子节点已存在" << std::endl;
                return false;
            }
            parent->left = new TreeNode(val);
        }
        else {
            if (parent->right != nullptr) {
                std::cout << "右子节点已存在" << std::endl;
                return false;
            }
            parent->right = new TreeNode(val);
        }
        return true;
    }

    // ========== 遍历操作 ==========

    /**
     * 前序遍历（递归）：根 -> 左 -> 右
     * 常用于复制树、计算前缀表达式等
     */
    void preorder() const {
        std::cout << "前序遍历(递归): ";
        preorderHelper(root);
        std::cout << std::endl;
    }

    /**
     * 前序遍历（非递归）：使用栈实现
     * 避免递归深度过大导致的栈溢出
     */
    void preorderIterative() const {
        std::cout << "前序遍历(非递归): ";
        if (root == nullptr) return;

        std::stack<TreeNode*> s;
        s.push(root);

        while (!s.empty()) {
            TreeNode* current = s.top();
            s.pop();
            std::cout << current->data << " ";

            // 先右后左，这样出栈时就是先左后右
            if (current->right != nullptr) {
                s.push(current->right);
            }
            if (current->left != nullptr) {
                s.push(current->left);
            }
        }
        std::cout << std::endl;
    }

    /**
     * 中序遍历（递归）：左 -> 根 -> 右
     * 对于二叉搜索树，中序遍历会得到有序序列
     */
    void inorder() const {
        std::cout << "中序遍历(递归): ";
        inorderHelper(root);
        std::cout << std::endl;
    }

    /**
     * 中序遍历（非递归）：使用栈实现
     */
    void inorderIterative() const {
        std::cout << "中序遍历(非递归): ";
        std::stack<TreeNode*> s;
        TreeNode* current = root;

        while (current != nullptr || !s.empty()) {
            // 一直向左走到尽头
            while (current != nullptr) {
                s.push(current);
                current = current->left;
            }

            // 访问节点并转向右子树
            current = s.top();
            s.pop();
            std::cout << current->data << " ";
            current = current->right;
        }
        std::cout << std::endl;
    }

    /**
     * 后序遍历（递归）：左 -> 右 -> 根
     * 常用于删除树、计算后缀表达式等
     */
    void postorder() const {
        std::cout << "后序遍历(递归): ";
        postorderHelper(root);
        std::cout << std::endl;
    }

    /**
     * 层次遍历：按层从上到下，从左到右访问
     * 使用队列实现，常用于计算树的高度、宽度等
     */
    void levelOrder() const {
        if (root == nullptr) {
            std::cout << "树为空" << std::endl;
            return;
        }

        std::cout << "层次遍历: ";
        std::queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* current = q.front();
            q.pop();
            std::cout << current->data << " ";

            if (current->left != nullptr) {
                q.push(current->left);
            }
            if (current->right != nullptr) {
                q.push(current->right);
            }
        }
        std::cout << std::endl;
    }

    // ========== 查询操作 ==========

    /**
     * 查找节点是否存在
     * @param val 要查找的值
     * @return 是否存在
     */
    bool contains(T val) const {
        return containsHelper(root, val);
    }

    /**
     * 获取树的高度（深度）
     * @return 树的高度
     */
    int height() const {
        return heightHelper(root);
    }

    /**
     * 获取节点数量
     * @return 节点总数
     */
    int size() const {
        return sizeHelper(root);
    }

    /**
     * 判断是否为叶子节点
     * @param val 节点值
     * @return 是否为叶子节点
     */
    bool isLeaf(T val) const {
        TreeNode* node = findNode(root, val);
        if (node == nullptr) return false;
        return node->left == nullptr && node->right == nullptr;
    }

    // ========== 工具函数 ==========

    /**
     * 清空树，释放所有内存
     */
    void clear() {
        clear(root);
        root = nullptr;
    }

    /**
     * 显示树的基本信息
     */
    void displayInfo() const {
        std::cout << "=== 树的基本信息 ===" << std::endl;
        std::cout << "是否为空: " << (isEmpty() ? "是" : "否") << std::endl;
        std::cout << "节点数量: " << size() << std::endl;
        std::cout << "树的高度: " << height() << std::endl;
        std::cout << "根节点值: " << (root ? root->data : T()) << std::endl;
        std::cout << "==================" << std::endl;
    }

private:
    // ========== 私有辅助函数 ==========

    /**
     * 递归前序遍历辅助函数
     */
    void preorderHelper(TreeNode* node) const {
        if (node == nullptr) return;
        std::cout << node->data << " ";  // 访问根节点
        preorderHelper(node->left);      // 遍历左子树
        preorderHelper(node->right);     // 遍历右子树
    }

    /**
     * 递归中序遍历辅助函数
     */
    void inorderHelper(TreeNode* node) const {
        if (node == nullptr) return;
        inorderHelper(node->left);       // 遍历左子树
        std::cout << node->data << " ";  // 访问根节点
        inorderHelper(node->right);      // 遍历右子树
    }

    /**
     * 递归后序遍历辅助函数
     */
    void postorderHelper(TreeNode* node) const {
        if (node == nullptr) return;
        postorderHelper(node->left);     // 遍历左子树
        postorderHelper(node->right);    // 遍历右子树
        std::cout << node->data << " ";  // 访问根节点
    }

    /**
     * 递归查找节点辅助函数
     */
    bool containsHelper(TreeNode* node, T val) const {
        if (node == nullptr) return false;
        if (node->data == val) return true;
        // 在左右子树中递归查找
        return containsHelper(node->left, val) || containsHelper(node->right, val);
    }

    /**
     * 递归查找节点指针辅助函数
     */
    TreeNode* findNode(TreeNode* node, T val) const {
        if (node == nullptr) return nullptr;
        if (node->data == val) return node;

        // 先在左子树中查找
        TreeNode* leftResult = findNode(node->left, val);
        if (leftResult != nullptr) return leftResult;

        // 左子树没找到，再在右子树中查找
        return findNode(node->right, val);
    }

    /**
     * 递归计算高度辅助函数
     */
    int heightHelper(TreeNode* node) const {
        if (node == nullptr) return 0;
        // 树的高度 = 1 + 左右子树高度的最大值
        return 1 + std::max(heightHelper(node->left), heightHelper(node->right));
    }

    /**
     * 递归计算节点数量辅助函数
     */
    int sizeHelper(TreeNode* node) const {
        if (node == nullptr) return 0;
        // 节点数量 = 1 + 左子树节点数 + 右子树节点数
        return 1 + sizeHelper(node->left) + sizeHelper(node->right);
    }

    /**
     * 递归清空树辅助函数（后序遍历方式删除）
     */
    void clear(TreeNode* node) {
        if (node == nullptr) return;
        clear(node->left);   // 先删除左子树
        clear(node->right);  // 再删除右子树
        delete node;         // 最后删除当前节点
    }
};

// ========== 使用示例 ==========
int main() {
    BinaryTree<int> tree;

    std::cout << "=== 创建二叉树 ===" << std::endl;

    // 使用层次插入构建完全二叉树
    tree.levelOrderInsert(1);  // 根节点
    tree.levelOrderInsert(2);
    tree.levelOrderInsert(3);
    tree.levelOrderInsert(4);
    tree.levelOrderInsert(5);
    tree.levelOrderInsert(6);
    tree.levelOrderInsert(7);

    // 显示树的基本信息
    tree.displayInfo();

    std::cout << "\n=== 遍历演示 ===" << std::endl;
    tree.preorder();            // 前序遍历  根->左->右

    tree.preorderIterative();   // 非递归前序遍历
    tree.inorder();             // 中序遍历 左->根->右

    tree.inorderIterative();    // 非递归中序遍历
    tree.postorder();           // 后序遍历 左->右->根

    tree.levelOrder();          // 层次遍历

    std::cout << "\n=== 查询操作 ===" << std::endl;
    std::cout << "包含 5: " << (tree.contains(5) ? "是" : "否") << std::endl;
    std::cout << "包含 10: " << (tree.contains(10) ? "是" : "否") << std::endl;
    std::cout << "4 是叶子节点: " << (tree.isLeaf(4) ? "是" : "否") << std::endl;
    std::cout << "2 是叶子节点: " << (tree.isLeaf(2) ? "是" : "否") << std::endl;

    std::cout << "\n=== 使用递归插入添加节点 ===" << std::endl;
    // 在节点2的右边插入8
    tree.recursiveInsert(2, 8, false);
    tree.levelOrder();

    std::cout << "\n=== 清空树 ===" << std::endl;
    tree.clear();
    tree.displayInfo();

    return 0;
}